Bias-Variance trade-off (theory)¶

As usual, we are given a dataset \(D=\{(x_1,y_1),\ldots,(x_n,y_n)\}\), drawn i.i.d. from some distribution \(P(X,Y)\). Throughout this lecture we assume a regression setting, i.e. \(y \in \mathbb{R}\). In this lecture we will decompose the generalization error of a classifier into three rather interpretable terms. Before we do that, let us consider that for any given input \(\mathbb{x}\) there might not exist a unique label \(y\). For example, if your vector \(\mathbb{x}\) describes features of house (e.g. #bedrooms, square footage, …) and the label \(y\) its price, you could imagine two houses with identical description selling for different prices. So for any given feature vector \(\mathbb{x}\), there is a distribution over possible labels. We therefore define the following, which will come in useful later on:

Expected Label (given \(\mathbb{x} \in \mathbb{R}^d\)):

\[\bar{y}(\mathbb{x}) = \mathbb{E}_{y|x}[Y] = \int_{y} y\,\text{Pr}(y|\mathbb{x}) \partial y.\]

The expected label denotes the label you would expect to obtain, given a feature vector \(\mathbb{x}\).

Alright, so we draw our training set \(D\), consisting of \(n\) inputs, i.i.d. from the distribution \(P\). As a second step we typically call some machine learning algorithm \(\mathcal{A}\) on this data set to learn a hypothesis (aka classifier). Formally, we denote this process as \(h_D=\mathcal{A}(D)\).

For a given \(h_D\), learned on data set \(D\) with algorithm \(\mathcal{A}\), we can compute the generalization error (as measured in squared loss) as follows:

Expected Test Error (given \(h_D\)):

\[\mathbb{E}_{(\mathbb{x},y)∼P} \Big[{(h_D(\mathbb{x})−y)}^{2}\Big]=\int_{x}\int_{y}{(h_D(\mathbb{x})−y)}^{2} \,\text{Pr}(\mathbb{x},y)\partial y \partial \mathbb{x}.\]

Note that one can use other loss functions. We use squared loss because it has nice mathematical properties, and it is also the most common loss function.

The previous statement is true for a given training set \(D\). However, remember that \(D\) itself is drawn from \(P^n\), and is therefore a random variable. Further, \(h_D\) is a function of \(D\), and is therefore also a random variable. And we can of course compute its expectation:

Expected Classifier (given \(\mathcal{A}\)):

\[\bar{h}=\mathbb{E}_{D∼P^n}[h_D]=\int_{D}h_D\, \text{Pr}(D)\partial D\]

where \(\text{Pr}(D)\) is the probability of drawing \(D\) from \(P^n\). Here, \(\bar{h}\) is a weighted average over functions.

We can also use the fact that \(h_D\) is a random variable to compute the expected test error only given \(\mathcal{A}\), taking the expectation also over \(D\).

Expected Test Error (given \(\mathcal{A}\)):

\[\mathbb{E}_{{(\mathbb{x},y)∼P}\atop{D∼P^n}} \, \Big[{(h_D(\mathbb{x})−y)}^2\Big] = \int_{D}\int_{\mathbb{x}}\int_{y} ({h_D(\mathbb{x})−y)}^2 \, \text{P}(\mathbb{x},y) \, \text{P}(D) \partial y \partial x \partial D\]

To be clear, \(D\) is our training points and the \((\mathbb{x},y)\) pairs are the test points.

We are interested in exactly this expression, because it evaluates the quality of a machine learning algorithm \(\mathcal{A}\) with respect to a data distribution \(P(X,Y)\). In the following we will show that this expression decomposes into three meaningful terms.

Decomposition of Expected Test Error¶

\[\begin{align*} \mathbb{E}_{\mathbb{x},y,D}\Big[[{h_D(\mathbb{x})−y]}^2 \Big] &= \mathbb{E}_{\mathbb{x},y,D}\Big[\big[{\big(h_D(\mathbb{x})−\bar{h}(\mathbb{x})\big)+\big(\bar{h}(\mathbb{x})−y\big)\big]}^2 \Big] \\ >&=\mathbb{E}_{\mathbb{x},D}[{(\bar{h}_D(\mathbb{x})−\bar{h}(\mathbb{x}))}^2] >+\mathbb{E}_{\mathbb{x},y}[{(\bar{h}(\mathbb{x})−y)}^2 ] + 2\, \mathbb{E}_{\mathbb{x},y,D}[(h_D(\mathbb{x})−\bar{h}(\mathbb{x}))(\bar{h}(\mathbb{x})−y)] >\end{align*}\]

The middle term of the above equation is 0 as we show below

\[\begin{align*} \mathbb{E}_{\mathbb{x},y,D} \Big[(h_D(x)−\bar{h}(\mathbb{x}))(\bar{h}(\mathbb{x})−y)\Big] &= \mathbb{E}_{\mathbb{x},y} \Big[\mathbb{E}_D[h_D(\mathbb{x})−\bar{h}(\mathbb{x})](\bar{h}(\mathbb{x})−y) \Big] \\ >&=\mathbb{E}_{\mathbb{x},y} \Big[(\mathbb{E}_D[h_D(\mathbb{x})]−\bar{h}(\mathbb{x}))(\bar{h}(\mathbb{x})−y) \Big] \\ >&=\mathbb{E}_{\mathbb{x},y} \Big[(\bar{h}(\mathbb{x})−\bar{h}(\mathbb{x}))(\bar{h}(\mathbb{x})−y) \Big] \\ >&=\mathbb{E}_{\mathbb{x},y}[0] \\ >&=0 >\end{align*}\]

Returning to the earlier expression, we’re left with the variance and another term

\[\begin{align*} \mathbb{E}_{x,y,D} \Big[({h_D(\mathbb{x})−y)}^2 \big] >&= \underbrace {\mathbb{E}_{\mathbb{x},D} \Big[ {(h_D(\mathbb{x})−\bar{h}(\mathbb{x}))}^2 \Big]}_{\text{Variance}}+\mathbb{E}_{\mathbb{x},y} \Big[ {(\bar{h}(\mathbb{x})−y)}^2 \Big] >\end{align*}\]

We can break down the second term in the above equation as follows:

\[\begin{align*} \mathbb{E}_{\mathbb{x},y} [{(\bar{h}(\mathbb{x})−y)}^2] >&=\mathbb{E}_{\mathbb{x},y} [{(\bar{h}(\mathbb{x})−\bar{y}(\mathbb{x}))+(\bar{y}(\mathbb{x})−y)}^2] \\ >&=\underbrace{ \mathbb{E}_{\mathbb{x},y} [{(\bar{y}(\mathbb{x})−y)}^2]}_{\text{Noise}} + \underbrace{ \mathbb{E}_{\mathbb{x}}[{(\bar{h}(\mathbb{x})−\bar{y}(\mathbb{x}))}^2] }_{\text{Bais}^2} + 2 \, \mathbb{E}_{\mathbb{x},y} [(\bar{h}(\mathbb{x})−\bar{y}(\mathbb{x}))(\bar{y}(\mathbb{x})−y)] >\end{align*}\]

The third term in the equation above is \(0\), as we show below

\[\begin{align*} \mathbb{E}_{\mathbb{x},y}[(\bar{h}(\mathbb{x})−\bar{y}(\mathbb{x}))(\bar{y}(\mathbb{x})−y)] >&=\mathbb{E}_{\mathbb{x}} [\mathbb{E}_{y∣\mathbb{x}} [\bar{y}(\mathbb{x})−y](\bar{h}(\mathbb{x})−\bar{y}(\mathbb{x}))] \\ >&=\mathbb{E}_{\mathbb{x}} [\mathbb{E}_{y∣\mathbb{x}} [\bar{y}(\mathbb{x})−y](\bar{h}(\mathbb{x})−\bar{y}(\mathbb{x}))] \\ >&=\mathbb{E}_{\mathbb{x}} [(\bar{y}(\mathbb{x})−\mathbb{E}_{y∣\mathbb{x}}[y])(\bar{h}(\mathbb{x})−\bar{y}(\mathbb{x}))] \\ >&=\mathbb{E}_{\mathbb{x}} [(\bar{y}(\mathbb{x})−\bar{y}(\mathbb{x}))(\bar{h}(\mathbb{x})−\bar{y}(\mathbb{x}))] \\ >&=\mathbb{E}_{\mathbb{x}}[0] \\ >&=0 >\end{align*}\]

This gives us the decomposition of expected test error as follows

\[\begin{align*} \underbrace{ \mathbb{E}_{\mathbb{x},y,D} \Big[{(h_D(\mathbb{x})−y)}^2 \Big] }_{\text{Expected Test Error}} = \underbrace{\mathbb{E}_{\mathbb{x},D} \Big[ {(h_D(\mathbb{x})−\bar{h}(\mathbb{x}))}^2\Big]}_{\text{Variance}} + \underbrace{ \mathbb{E}_{\mathbb{x}} \Big[{(\bar{h}(\mathbb{x})−\bar{y}(\mathbb{x}))}^2\Big] }_{\text{Bias}^2} + \underbrace{ \mathbb{E}_{\mathbb{x},y}\Big[(\bar{y}(x)−y)^2\Big] }_{\text{Noise}} >\end{align*}\]

Variance: Captures how much your classifier changes if you train on a different training set. How “over-specialized” is your classifier to a particular training set (overfitting)? If we have the best possible model for our training data, how far off are we from the average classifier?

Bias: What is the inherent error that you obtain from your classifier even with infinite training data? This is due to your classifier being “biased” to a particular kind of solution (e.g. linear classifier). In other words, bias is inherent to your model.

Noise: How big is the data-intrinsic noise? This error measures ambiguity due to your data distribution and feature representation. You can never beat this, it is an aspect of the data.